//Given a string containing digits from 2-9 inclusive, return all possible lette
//r combinations that the number could represent. Return the answer in any order. 
//
//
// A mapping of digit to letters (just like on the telephone buttons) is given b
//elow. Note that 1 does not map to any letters. 
//
// 
//
// 
// Example 1: 
//
// 
//Input: digits = "23"
//Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
// 
//
// Example 2: 
//
// 
//Input: digits = ""
//Output: []
// 
//
// Example 3: 
//
// 
//Input: digits = "2"
//Output: ["a","b","c"]
// 
//
// 
// Constraints: 
//
// 
// 0 <= digits.length <= 4 
// digits[i] is a digit in the range ['2', '9']. 
// 
// Related Topics 深度优先搜索 递归 字符串 回溯算法 
// 👍 1308 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：Letter Combinations of a Phone Number
 class P17LetterCombinationsOfAPhoneNumber {
    public static void main(String[] args) {
        Solution solution = new P17LetterCombinationsOfAPhoneNumber().new Solution();
        // TO TEST
        System.out.println(solution.letterCombinations("3"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        String[] arr = new String[]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        public List<String> letterCombinations(String digits) {
            List<String> result = new ArrayList<>();
            if (digits == null || digits.length() == 0) {
                return result;
            }

            letterCombinations(digits, 0, result, new StringBuilder());
            return result;
        }


        private void letterCombinations(String digits, int i, List<String> result, StringBuilder stringBuilder) {

            if (i >= digits.length()) {
                result.add(stringBuilder.toString());
                return;
            }
            int index = (digits.charAt(i) - '1') - 1;
            String s = arr[index];
            for (int j = 0; j < s.length(); j++) {
                char c = s.charAt(j);
                stringBuilder.append(c);
                letterCombinations(digits, i+1, result, stringBuilder);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}